package leetcode.递归回溯BFSDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * 17. 组合
 *
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 */
public class Test77组合 {

    /**
     * n = 3, k = 2
     * 1,2,3
     * 假设第一次选择的是 1 然后需要在2、3中遍历一次得到12、13
     * 假设第一次选择的是 2，则它只能在3中遍历一次得到23，为什么不是在1、3中遍历，因为
     * 稍后会遍历到 1 的，1 的匹配选择在2、3里面。已经包含了答案。则2就不需要再重复1会处理的答案了
     */


    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        if (n <= 0 || k <= 0) {
            return ans;
        }
        dp(n, k, 1, ans, new ArrayList<>());
        return ans;
    }

    // 在n个数据中寻找k个数的组合，从给定的start处开始遍历
    public static void dp(int n, int k, int start, List<List<Integer>> ans, List<Integer> temp) {
        // temp 存储满了就添加到结果集中
        if (temp.size() == k) {
            ans.add(new ArrayList<>(temp));
            return;
        }

        // 本用例其实不需要遍历到 i=3 的
        // 所以需要剪枝
        // 剪枝就是提前结束du对 i 的判断，
        for (int i = start; i <= n; i++) {
            temp.add(i);
            dp(n, k, i + 1, ans, temp);
            temp.remove(temp.size() - 1);
        }
    }


    public static void main(String[] args) {
        System.out.println(combine(3, 2));
    }
}
